package epsofts.Neutron;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * @version 1.0
 * @created 14-sept.-2006 22:48:08
 */
public class JoueurUCT implements IJoueur
{
	public static final String	LABEL						= "CPU (UCT)";

	public static final Boolean	ENABLED						= true;

	public static final float	INFINI						= Float.MAX_VALUE - 10;

	private static final Random	random						= new Random();	

	/**
	 * Thread AlphaBeta.
	 */
	private Thread				m_thUCT				= null;
	
	private int m_iTimeOut;
	private short m_iGenerationsAleatoires;
	
	/**
	 * Nombre de coups évalués.
	 */
	private int					m_nbCoupsEvalues			= 0;
	private int					m_profondeurMax				= 0;

	/**
	 * Foncteur impl�mentant la fonction d'�valuation.
	 */
	private final IEvalueur		m_Evalueur;

	public JoueurUCT(int i_iTimeOut, IEvalueur i_evalueur, short i_GenerationsAleatoires)
	{
		m_iTimeOut = i_iTimeOut;
		m_iGenerationsAleatoires = i_GenerationsAleatoires;
		m_Evalueur = i_evalueur;
	}

	Coup m_meilleurCoup;
	
	/**
	 * Donne le tour de jeu au joueur (pour le plateau donn�) et attend une proposition de mouvement (Coup).
	 * 
	 * @param plateau
	 */
	public Coup Jouer(final Plateau plateau) throws InterruptedException
	{
		if (m_thUCT != null) throw new RuntimeException("Joueur déjà en train de jouer");

		if (plateau.getGeneration() < m_iGenerationsAleatoires)
		{
			Set<Coup> coups = plateau.listerCoups();
			Coup coup = null;
			eCase estTerminal = eCase.NEUTRON;

			do
			{
				coup = (Coup) coups.toArray()[random.nextInt(coups.size())];
				estTerminal = plateau.jouerCoup(coup).testerPlateauTerminal(true); // TODO ici ?
			} while (estTerminal != eCase.VIDE);
			return coup;
		}

		m_thUCT = new Thread(new Runnable()
		{
			public void run()
			{
				try
				{
					m_meilleurCoup = UCTSearch(m_iTimeOut, plateau);
				}
				catch(InterruptedException e)
				{
					System.out.println("UCT interrupted");
				}
			}
		});

		m_thUCT.setName("Thread UCT");
		m_thUCT.setPriority(Thread.MAX_PRIORITY);
		m_nbCoupsEvalues = 0;
		m_profondeurMax = 0;
		
		long time = System.currentTimeMillis();
		m_thUCT.start();

		try
		{
			m_thUCT.join();
			time = System.currentTimeMillis() - time;
		}
		catch (InterruptedException e)
		{
			m_thUCT.interrupt();
			
			m_thUCT.join();
			m_thUCT = null;
			throw e;
		}
		m_thUCT = null;
		System.out.format("JoueurUCT      ] nb de coups évalués : %d; profonfeur : %d; %.2fs\n", m_nbCoupsEvalues, m_profondeurMax, ((float) time/1000));
		return m_meilleurCoup;
	}

	/**
	 * Doit tnterrompre le tour du joueur si celui-ci �tait en train de jouer.
	 */
	public void Stopper()
	{
		//TODO: ne sert à rien (déjà interrompu à ce stade)
		System.out.println("Stopper JoueurUCT (nothing to do)");
		//m_thAlphaBeta.interrupt();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see Neutron.IJoueur#OnJeuFini(Neutron.eCase)
	 */
	public void OnJeuFini(eCase i_vainqueur)
	{
		if ((m_thUCT != null) && m_thUCT.isAlive() && !m_thUCT.isInterrupted())
		{
			Stopper();
		}
	}

	/**
	 * Teste d'abord si le plateau est terminal, sinon apelle l'Evalueur.
	 * 
	 * @param plateau
	 *            Plateau � �valuer.
	 * @return score du plateau (de -INFINI � +INFINI).
	 */
	private float Evaluer(final Plateau plateau)
	{
		eCase base = plateau.testerPlateauTerminal(false); // TODO ici ?
		switch (base)
		{
		case ROUGE:
			return +INFINI;
		case BLEUE:
			return -INFINI;
		default:
			return m_Evalueur.evalueurPlateau(plateau);
		}
	}

	private static class Node
	{
		public int wins = 0;
		public int visits=0;
		
		private short depth=0;
		
		public Plateau plateau;
		public Coup coup;
		
		public Node child;
		public Node sibling;
		
		public Node(Plateau plateau)
		{
			this(plateau, (short) 0, null);
		}
		
		public Node(Plateau plateau, short depth, Coup coup)
		{
			this.plateau = plateau;
			this.depth = depth;
			this.coup = coup;
		}
		
		public void createChildren()
		{
			Node last = null;
			Set<Coup> coups = plateau.listerCoups();
			for(Coup c : coups)
			{
				Node n = new Node(plateau.jouerCoup(c), (short) (depth+1), c);
				
				if (last == null) child = n;
				else last.sibling = n;
				
				last = n;
			}
		}
		
		public void update(int val)
		{						
			visits++;
			wins+=val;
		}
		
		public double getWinRate()
		{
			if (visits > 0) return (double) wins / visits;
			else return 0;
		}
		
		public Node getBestChild()
		{
			Node currentChild = child;
			Node bestChild = null;
			int bestVisits = -1;
			while(currentChild != null)
			{
				if (currentChild.visits > bestVisits)
				{
					bestChild = currentChild;
					bestVisits = currentChild.visits;
				}
				currentChild = currentChild.sibling;
			}
			return bestChild;
		}
	}
	
	// Larger values give uniform search, Smaller values give very selective search
	public static final double UCTK = 0.44;
	
	private Node root = null;
	
	public Coup UCTSearch(int timeOut, Plateau plateau) throws InterruptedException
	{
		root = new Node(plateau);
		root.createChildren();
		int minSim = 30;
		int iSim = 0;
		
		long start = System.currentTimeMillis();
		while(System.currentTimeMillis() - start < timeOut || iSim < minSim)
		{
			if (m_thUCT.isInterrupted())
			{
				throw new InterruptedException();
			}
			
			playSimulation(root);
			++iSim;
		}
		
		Node n = root.getBestChild();
		return n.coup;
	}
	
	private int playSimulation(Node n)
	{
		int randomResult = 0;
		if (n.visits < 10)
		{
			// 10 simulations untill children are expanded (saves memory)
			randomResult = playRandomGame(n);
		}
		else if (n.child == null)
		{
			n.createChildren();
		}
		
		if (n.child == null)
		{			
			randomResult = playRandomGame(n);
		}
		else
		{
			Node next = UCTSelect(n);
			if (next == null) {throw new Error("Error, je suis codé avec les pieds.");}
			
			int res = playSimulation(next);
			randomResult = 1 - res;
		}
		
		n.update(1-randomResult);
		m_profondeurMax = Math.max(m_profondeurMax, n.depth);
		return randomResult;
	}

	private Node UCTSelect(Node node)
	{
		Node res = null;
		Node next = node.child;
		double bestUCT=0;
		
		while(next!=null)
		{						
			double uctValue;
			if (next.visits > 0)
			{
				double winRate = next.getWinRate();
				double uct = UCTK * Math.sqrt(Math.log(node.visits) / next.visits);
				uctValue = winRate + uct;
			}
			else
			{
				// Always play a random unexplored move first.
				uctValue = 10000 + 10000*Math.random();
			}
			
			if (uctValue >= bestUCT)
			{
				bestUCT = uctValue;
				res = next;
			}
			
			next = next.sibling;
		}
		
		return res;
	}
	
	private int playRandomGame(Node n)
	{
		++m_nbCoupsEvalues;
		return (Evaluer(n.plateau) > 0 && n.plateau.getTour() == eCase.ROUGE)?1:0;
	}

}
